The present patent application is related to the following patent applications which are being filed simultaneously (and are hereby incorporated herein) and are assigned to the same entity, Motorola, Inc.: CR00193M, Method, Device and Article of Manufacture for Implementing a Real-Time Task Scheduling Accelerator, by Brett Louis Lindsley, Uri Dayan and Moshe Tarrab; CR00194M, Method, Device and Article of Manufacture for Specifying and Controlling a Task Switch from an External Device in a Multi-Tasking Preemptive Priority-Based Real-Time Operating System, by Brett Louis Lindsley and Ed Martinez; CR00195M, Method, Device and Article of Manufacture for Clearing Command Bits in a Task Scheduling Device for a Multi-Tasking Preemptive Priority-Based Real-Time Operating System, by Brett Louis Lindsley; and CR00196M, Method, Device and Article of Manufacture for Efficient Data Queuing Using Hardware Queue Pointers and a Software Interrupt Service Routine in a Multi-Tasking Preemptive Priority-Based Real-Time Operating System, by Brett Louis Lindsley.
The field of the invention relates to multiple task execution processors, in particular, a multi-task execution processor having a preemptive prioritized task scheduling system.
Multi-tasking is the capability of a single processor to execute multiple tasks concurrently. A processor performs multi-tasking execution by switching between tasks using a defined set of multi-tasking rules. For theoretical reasons, real-time multi-tasking systems preferably use a set of rules where tasks are prioritized. Lower priority tasks can be preempted (forcibly switched) to execute a higher priority task if necessary. This xe2x80x9cpreemptive prioritizedxe2x80x9d system always executes the highest priority ready task.
A xe2x80x9ctaskxe2x80x9d is defined as an independent entity of computing. For example, where a computer system permits many users on different terminals access to the same processor, the computer system assigns a unique task to each user""s computing (where each user""s computing is unrelated to another user""s computing). Generally, a task unit contains an entry for each task. Tasks are typically synchronized using xe2x80x9ceventsxe2x80x9d An event is used to indicate that an activity has taken place, such as data arrival, time-out, etc. Thus, an event may indicate execution of a task, an interrupt service routine or the like. Events are counted using semaphores. Semaphores synchronize the event producer and the event consumer as shown in FIG. 2, numeral 200.
Events are generated by tasks 201 or interrupt service routines (ISRs) 202. ISRs are not allowed to consume events because ISRs are not scheduled and execute outside of the normal task scheduling environment of the processor. However, ISRs are allowed to generate events to indicate the status of the cause of the interrupt.
A counting semaphore 203 allows a plurality of events to be generated without being lost. Similarly, a plurality of tasks may be waiting for the same event. When the semaphore counter is positive, it indicates events have been produced but no tasks are waiting for the events. When the semaphore counter is zero, it indicates no events have been generated and no tasks are waiting. When the semaphore counter is negative, it indicates there are no events generated but a plurality of tasks are waiting for the events. The process of generating an event to a semaphore is typically called xe2x80x9cpostingxe2x80x9d the event 204. The process of waiting for an event from a semaphore is typically called xe2x80x9cpendingxe2x80x9d for the event 205.
When an event is generated for a semaphore that has a list of tasks pending, the task 206 at the head of the list becomes ready for execution. At this time, the task scheduling function 207 must determine if this task should be selected for execution or if it should be put in a list with other ready tasks to be executed at a later time. This decision is based on the priority of the task that is currently executing compared to the priority of the task that has just become ready.
If the task that has just become ready is the same or lower priority than the currently executing task, the currently executing task continues executing. The new ready task is moved to a list to be executed at a later time.
If the task that has just become ready is a higher priority than the currently executing task, the currently executing task is preempted to allow the new ready task to execute. Thus, the highest priority ready task 208 is always selected for execution.
At some time, the currently executing task completes its computation and becomes inactive. A task becomes inactive by pending on a semaphore when the semaphore count is zero or negative. For example, a semaphore may represent data buffers that require processing. If the task that processes data buffers pends for the semaphore that represents data buffers, the task is synchronized to the data buffer generation. If data buffers are available, the semaphore count is greater than zero. Task pend requests on the semaphore allow the task to continue. If data buffers are not available, the semaphore count is less than or equal to zero. When the task pends on the semaphore with a count that is less than or equal to zero, the task does not have data for processing and will block execution.
At the point when a task pends on a semaphore with zero or negative count, the task that has made the request is not allowed to continue execution and must xe2x80x9cblockxe2x80x9d The task scheduling function stops this task and selects another task s for execution. The task scheduling function looks at other ready tasks at the same or lower priorities to determine the next highest priority ready task. If a task is found, it is selected for execution. If a task is not found, the processor is put into an idle state until a task becomes ready.
Although the task selection process is easy to understand, in a practical environment this can lead to significant inefficiencies. For example, the following cause inefficiencies in a preemptive prioritized task scheduling system:
Each time a semaphore is processed, there is a potential for a task change. This causes the scheduling function to be called quite often when many times there is no change.
When a task pends for a semaphore and blocks, the scheduler must perform a search algorithm to determine the next ready task. If there are a large number of tasks and priority levels, this activity may be time-consuming.
The process of searching for a task may have variable timing making task scheduling functions non-deterministic.
The task scheduler must obtain control of the processor to switch tasks.
In a software task scheduling system, interrupt service routines typically require entry and exit code to flag interrupt usage and nesting. The flagging is typically used to call the scheduler to determine if the interrupt generated an event that may have changed execution. The use of entry and exit code consumes time and is undesirable when processing interrupts.
Solutions to the problems set forth above typically involve constraining the functionality of the scheduler. These constraints may include limiting the number of tasks, limiting the number of priority levels, limiting the number of tasks at each priority level, limiting the representation range of the semaphore counter, etc. It is undesirable to have such constraints in a system because such constraints may restrict the type of system that can be supported.
Thus, there is a need for a method, device and article of manufacture that optimizes real-time multi-tasking for a processor.